package LeetCode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 15. 三数之和
 * https://leetcode.cn/problems/3sum/description/
 * err
 */

class Solution5 {
    public static void main(String[] args) {
        int[] arr = {-1,0,1,2,-1,-4};
        threeSum(arr);
    }
    public static List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);//给数组排升序
        List<List<Integer>> list = new ArrayList<List<Integer>>();
        int len = nums.length;
        for(int i = 0; i < len - 3; i++) {
            List<Integer> tmp = new ArrayList<>();
            //固定i，求i+1到最后一个位置，找出所有可能的组合，即求i+1到最后一个位置+i等于0的所有组合。
            int left = i + 1;
            int right = len - 1;
            int ii = 0 - nums[i];//此时i位置的相反数
            //求i+1到len-1位置两数相加等于ii的所有组合，双指针求法
            while(left < right) {
                if(nums[left] + nums[right] < ii) {
                    left++;
                } else if(nums[left] + nums[right] > ii) {
                    right--;
                } else {
                    //找到符合题目要求的三元组
                    tmp.add(i);
                    tmp.add(left);
                    tmp.add(right);
                    while(nums[left + 1] == nums[left]) {
                        left++;
                        //处理越界情况
                        if(left >= right) {
                            break;
                        }
                    }
                    left++;
                    while(nums[right + 1] == nums[right]) {
                        right--;
                        //处理越界情况
                        if(left >= right) {
                            break;
                        }
                    }
                    right--;
                }
            }
            list.add(tmp);
        }
        return list;
    }
}